package partition;

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Random;

public class Solution {
      public class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }
    public ListNode partition(ListNode head, int x) {
        ListNode dummyL = new ListNode();
        ListNode dummyR = new ListNode();
        ListNode pl = dummyL;
        ListNode pr = dummyR;
        ListNode p = head;
        while (p!=null) {
            if(p.val<x) {
                pl.next = p;
                pl = pl.next;
            } else {
                pr.next = p;
                pr = pr.next;
            }
            p = p.next;
        }
        pl.next = dummyR.next;
        pr.next = null;
        return dummyL.next;
    }
    public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
    public ListNode reverseBetween(ListNode head, int left, int right) {
          ListNode dummy = new ListNode(-1);
          ListNode start = head;
          dummy.next = head;
          ListNode prev = dummy;
          int i = 1;
          for ( i = 1; i < left; i++) {
              prev = start;
              start = start.next;
          }
          ListNode next = null;
          ListNode cur = start;
        for ( i = left; i <= right; i++) {
            ListNode tmp = cur.next;
            cur.next = next;
            next = cur;
            cur = tmp;
        }
        prev.next.next = cur;
        prev.next = next;
        return dummy.next;
    }

    public TreeNode sortedListToBST(ListNode head) {
          return dfs(head,null);
    }
    private TreeNode dfs(ListNode head,ListNode end) {
          if(head.val>end.val) return null;
          if(head == end) return new TreeNode(head.val);
          ListNode slow = head;
          ListNode fast = head;
          while (fast!=end&&fast.next!=null) {
              slow = slow.next;
              fast = fast.next.next;
          }
          TreeNode root = new TreeNode(slow.val);
          root.left = dfs(head,slow);
          root.right = dfs(slow.next,end);
          return root;
    }
    class Node {
        public int val;
        public Node left;
        public Node right;
        public Node next;

        public Node() {}

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, Node _left, Node _right, Node _next) {
            val = _val;
            left = _left;
            right = _right;
            next = _next;
        }
    };
    public Node connect(Node root) {
        Queue<Node> queue = new ArrayDeque<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int size = queue.size(); // 当前层的节点数量
            for (int i = 0; i < size; i++) {
                Node p = queue.poll();
                if(i!=size-1) {
                    p.next = queue.peek();
                }
                if(p.left!=null)queue.add(p.left);
                if(p.right!=null)queue.add(p.right);
            }
        }
        return root;
    }

    public ListNode sortList(ListNode head) {
        return merge(head,null);
    }
    public ListNode merge(ListNode head,ListNode tail){
        if(head == tail){
            return head;
        }
        ListNode mid = getMiddle(head,tail);
        ListNode r = merge(mid.next,tail);
        mid.next = null;
        ListNode l = merge(head,mid);
        return mergeTwoList(l,r);
    }
    private ListNode getMiddle(ListNode head,ListNode tail){
        ListNode slow = head;
        ListNode fast = tail;
        while (fast!=tail){
            slow = slow.next;
            fast = fast.next;
            if(fast!=tail){
                fast = fast.next;
            }
        }
        return slow;
    }
    private ListNode mergeTwoList(ListNode a,ListNode b){
        ListNode dummy = new ListNode();
        ListNode p = dummy;
        ListNode p1 = a;
        ListNode p2 = b;
        while (p1!=null||p2!=null){
            if(p1 == null){
                p.next = p2;
                break;
            }
            if(p2 == null){
                p.next = p1;
                break;
            }
            if(p1.val<p2.val){
                p.next = p1;
                p1=p1.next;
            }else {
                p.next=p2;
                p2=p2.next;
            }
        }
        return dummy.next;
    }


    ListNode head;
    public Solution(ListNode head) {
        this.head = head;
    }

    public int getRandom() {
        // 水塘抽样算法
        // 第i个元素的概率是
        int i = 1;
        int ans = 0;
        Random random = new Random();
        ListNode p = head;
        while (p!=null){
            if(i == 1){
                ans = p.val;
            } else if (random.nextInt(i) < 1) {
                ans = p.val;
            }
            i++;
            p = p.next;
        }
        return ans;
    }
    public ListNode[] getRandom(int k){
        ListNode p = head;
        Random random = new Random();
        ListNode[] ans = new ListNode[k];
        int cur = 1;
        while (p!=null){
            if(cur-1<k){
                // 水塘没满 直接加水
                ans[cur-1] = p;
            } else if (random.nextInt(cur)<k){    // 水塘满了 该点被选择的概率为 k/cur
                ans[random.nextInt(k)] = p;
            }
            p = p.next;
        }
        return ans;
    }
}
